T=20;
n=[92,100,99,91,91,99,92,93,98,96,94,100,94,99,99,94,100,100,95,100];
a=[10288,2684,13484,10687,9690,16088,7887,6087,2289,6687,13689,14686,12284,8889,2484,7085,14484,14086,6490,14286,4888,7286,17489,9088,6286,5489,16687,17288,9287,10887,15287,12687,8286,17688,17884,4085,15887,4284,5688,5285,11286,14887,16486,11487,19487,2086,3889,3087,19086,18884,12088,5088,15485,13886,15088,11686,2888,8084,4687,18287,16887,15687,12885,18490,3290,8684,1686,13088,9490,12484,3487,19688,5885,10085,1885,17084,8484,7686,4487,11085,10490,3690,6887,13288,18684,19289,1489,18087,16290,11887,9890,7488,3982,9382,17182,3182,20782,7182,10982,14782,5582,9582,4982,10382,12182,9182,20582,6982,3782,13382,15782,2382,19182,18982,19982,6782,13782,6182,13182,5382,18182,20982,19582,21182,10582,7582,15582,11782,14182,16382,20182,14382,11382,12782,3382,7982,12382,15182,2782,17582,8582,7382,10782,18782,2982,12982,9782,9982,20382,5982,16582,19382,10182,14582,8782,2182,13982,21382,7782,15382,8982,17382,12582,14982,18382,16182,4782,8382,16982,5782,4182,8182,4382,13582,21782,5182,3582,17782,16782,21582,4582,6382,19782,17982,11582,6582,15982,2582,1982,11982,18582,11182,11099,20098,4699,13094,15894,5695,6696,1499,7097,4095,14895,3299,20897,3496,4897,13497,11295,18297,14700,17300,9496,13894,2699,12500,17695,12099,19496,6096,2500,12897,14094,20696,16500,19897,14498,6897,15699,5497,5897,3898,5294,11894,4294,15500,17896,13699,20498,4494,3699,5094,2898,20299,18497,1895,7497,9099,15096,8898,10098,10695,18895,1696,6498,16696,7295,11500,16097,10298,12298,16899,18097,9895,8097,7898,8498,21095,16296,19094,7700,6294,10899,8699,3098,19299,14300,9297,19699,11699,18699,2094,10499,2295,8298,17495,17094,12696,9694,13299,15296,16440,8445,13037,5648,18834,7642,2843,15043,18047,6848,6443,6233,19843,17032,5842,18439,5433,14644,2038,3438,13833,1844,12046,3242,17443,13237,14445,15441,12232,3047,16834,5037,7241,13444,17843,6634,15836,3639,11040,7836,16243,9635,13634,3839,9240,19633,11243,9040,18647,6046,8638,4840,12436,15244,2634,5238,12839,14843,12637,2238,7443,8040,17248,9443,11842,8234,10836,17638,11446,4239,9837,10234,18240,10634,14234,19039,15643,4443,19448,16045,19239,7045,4040,10439,16648,14040,4643,8846,11648,10039,2447,15113,14313,5514,2519,6519,2314,14518,1916,2912,12717,7519,18512,16516,2117,9514,3318,13719,15512,7118,15918,10714,12312,3518,8916,8312,3919,10517,11518,19317,12915,10118,17512,5718,11113,12519,4719,14919,14712,13315,3119,7917,18113,8115,4113,14113,17315,10919,5919,15319,3717,19715,13518,2712,18718,13117,4316,18916,4512,10312,16319,19914,7313,5112,16115,12116,17117,18318,16919,6714,11913,8715,9919,6919,19517,16715,6315,19114,13912,15719,7715,6115,17717,11314,9113,8519,17916,11713,5318,4918,9719,9317,19197,2997,18192,1994,16592,5199,4797,18799,9597,2598,11999,19796,10599,11200,6598,11796,14196,6393,3200,16997,5396,16799,5996,9994,17194,1595,1798,18996,8794,12793,7792,14997,18394,5592,12393,12992,19998,19592,10393,13197,13600,7194,12597,4599,8397,19392,20196,20399,9392,13394,7400,3796,10999,8596,11393,15793,6798,3600,15394,6195,14392,7000,8992,16399,4192,18596,17594,4396,12198,1198,10193,15993,20599,9199,2199,17795,10792,15192,3999,1396,9796,8194,3397,14596,17392,4994,5793,2797,20800,13798,16193,11596,7999,14000,7593,14800,18000,2399,15595,16436,1634,3233,17037,15039,7439,7033,9435,2441,16033,4036,15236,9237,12239,9637,14634,16240,5433,14433,6836,5241,9035,7239,6039,7838,8441,3833,19836,5840,18041,10435,3634,9838,8041,19239,19634,4239,17237,6639,2235,2836,14235,18635,13235,14840,16838,10636,19435,5033,2639,12438,17436,13034,3433,5634,10034,19039,12835,10236,6239,12033,6439,13639,15437,15837,10834,18236,18436,1839,3033,7635,14040,18841,17641,2036,11038,4835,11633,15639,11833,17836,8239,4634,16639,13835,11238,13440,8641,4439,12638,11441,8837,18566,12366,12762,15166,11966,16165,7364,16362,13166,15764,16563,10565,2164,17166,14166,4764,2766,19363,19565,5365,9162,4163,6164,3766,19166,6562,3564,7166,13965,16964,4962,8365,14363,10964,12562,17365,3362,13763,12965,12163,8164,1763,10766,5766,4365,3965,5566,7563,15966,4562,6364,14763,18762,2362,14566,11766,2964,6766,8966,18166,7764,17965,10163,15363,5963,7964,15565,8762,10364,17563,9766,13562,2565,8563,9564,16764,11564,5164,6962,17765,11366,19764,18963,11163,1565,18364,14966,3165,13362,1966,9365,9963,19966,15694,14894,4494,10294,5694,2894,17694,3894,8694,2094,3094,7494,19094,17294,13494,4094,20094,18294,14094,10694,9094,1894,18094,12294,6294,4694,11294,7894,15294,10894,20894,5294,14694,8094,8294,9494,12494,5894,13094,19494,5494,1494,17494,7694,9894,2294,20494,20694,16094,9694,9294,11094,18694,8494,4894,12694,20294,19694,19294,17094,16294,16694,3494,15894,13294,11894,16494,8894,16894,7294,6694,2694,3294,12094,6094,14294,15494,2494,10494,14494,18494,7094,13894,18894,12894,17894,6894,1694,5094,10094,11694,3694,4294,19894,6494,15094,11494,13694,3265,14867,12869,10868,8669,5468,20271,6270,16065,17070,15063,5666,10065,4469,18865,14263,17264,9063,3670,8271,16468,7064,5071,18668,17464,11870,7464,4064,3066,19664,2871,18065,7267,4865,6867,7666,20863,5263,13063,3871,9268,1867,18267,11266,4669,10465,13865,6665,6466,10266,2067,14468,9668,15468,15668,11071,20469,17866,11470,12464,16871,17670,8068,4264,15268,12267,2663,2469,9866,11669,12665,20667,14063,20071,13664,14665,19866,7865,19067,15866,6071,19267,8868,5863,8469,16665,19466,18466,12069,13471,16267,2271,13265,3471,10668,9467,5541,20140,8330,11527,3542,19536,2142,8729,2942,16926,13330,8535,6745,11330,17538,17726,10135,9927,19934,9738,13542,12731,1932,14328,14130,9328,19132,7941,5931,10940,18145,6534,13944,11730,12344,11932,2333,4326,4739,7140,4128,13732,17143,3343,10334,7544,14940,20329,3137,15135,13134,12937,5129,18545,18944,7742,3927,11145,3730,14533,2544,5737,4944,16330,15745,15538,8144,12545,19327,10537,15933,8937,20526,6134,4545,14743,2729,15330,17336,9140,7331,16143,19742,5341,12140,18339,16527,6339,16726,10744,6926,9529,17944,18737,11992,3992,15591,17588,5188,3392,13189,12791,8791,7590,5389,9389,6189,11391,7191,16188,20388,7790,20189,12992,5589,14591,20591,6988,7991,8392,19189,13590,8188,12590,4190,4388,12390,18992,10589,8589,2189,15190,4591,20791,6592,19992,1789,5791,8988,5988,17791,18192,1589,10192,16591,15991,2389,16990,1990,4991,13392,9590,11191,13990,17992,19388,11590,10989,14188,16789,21188,18592,10391,19788,3788,13788,15389,15791,20992,4792,16391,2589,1391,19588,2792,3592,2991,6388,3188,18390,17389,10792,7392,17189,9792,14791,6792,18792,12191,11790,14391,9991,14991,9192,11030,5828,3022,17233,7417,4228,14830,9632,4033,17622,12235,9431,7624,13635,2034,5618,15022,7235,16232,12424,15826,2620,16822,9233,3616,6025,10226,17432,1830,18435,15629,17822,10427,16033,14033,14632,18633,11617,13029,3819,18024,17018,15417,5027,1619,13817,19626,18222,4419,2821,20026,20225,2417,11417,15221,6620,12633,7827,12825,14232,3429,19031,12024,3231,7032,11827,5422,13223,9835,19828,16622,2230,19430,8830,6225,4834,4630,8224,19225,9018,16433,11232,10631,14429,5233,10033,8623,13426,6832,18820,8418,6434,8016,10819,17907,11909,15303,20903,18905,15906,9103,18504,4305,15707,1909,17106,2902,19502,9307,6104,5105,13507,10309,14508,4504,7107,13303,14107,21303,14902,16306,2301,10707,13709,2104,11704,21504,19101,20301,3108,3902,4707,8708,16109,11508,15508,3305,8503,8902,13906,21108,10109,7505,7905,12107,3705,4901,10904,9509,19306,6703,12703,12506,5908,12307,16503,2502,6303,8309,19905,17301,4109,10504,16902,14706,20501,7308,18309,12908,5704,14307,15101,20101,3504,11108,6502,17503,18707,7705,20702,8101,2705,16704,11301,5306,9707,18102,19709,13108,5505,9904,6903,17702,9357,17357,14555,18353,20354,7153,9952,5954,2354,3952,14352,19354,19756,6554,13157,13757,4157,19954,2152,12557,4553,5753,4357,6152,16356,6757,12753,11755,16954,12154,6952,3553,8556,3152,20156,8954,11353,13355,1755,13954,17153,14953,11954,20556,18553,3352,10355,8756,14755,15555,18953,5157,6355,10957,14156,7554,15755,13556,12352,7353,5353,3756,12957,7754,1554,16556,2955,19156,9556,17755,18157,9153,1352,10152,10552,15355,10757,17557,17954,16155,2753,2554,1156,15155,5552,7953,20755,8356,4954,9752,8152,19553,16757,1953,15953,11555,11156,4754,18757,8589,19984,18394,15391,2587,19784,7586,18190,11794,16391,2190,8786,16990,5591,13586,11994,12592,17588,12194,7793,5385,18992,9592,11592,12989,11390,7186,10187,14193,20184,10384,9388,15189,14992,4386,4989,13984,8386,3194,12790,13392,17793,3989,2786,15584,6790,6188,4194,8186,1987,4588,10591,13793,10789,9785,9192,14587,6590,16587,16786,16194,1787,17184,7988,6994,17392,5984,3791,5189,15793,8987,19387,2994,7385,15990,13186,19194,19587,5790,11188,17986,4790,20393,12387,10990,18789,3391,14394,18594,2392,9987,14788,6391,3593,5327,6342,8729,2541,18526,2726,12132,4531,14740,18742,12534,14142,21334,4344,11344,17929,3736,20935,14338,19330,11743,7338,17542,2126,19737,2926,20744,3532,15142,10335,20540,14931,21538,5731,16737,16530,5543,6926,6730,10939,4130,6135,2342,16140,8133,21128,9528,15929,10729,4929,11528,1944,5940,8343,12731,10135,19142,7944,13533,9727,20139,14532,13133,6538,15344,20328,13944,19528,4739,8944,16932,12943,17341,16344,3144,7530,13343,7726,5139,12342,8526,9132,15733,21744,9930,18333,7137,10528,18136,18936,13734,11934,3343,11135,17731,17137,19934,9332,3944,15539,21796,5793,18997,17400,14605,11201,13595,14802,10200,9994,3204,4193,2998,11602,11000,15402,8805,16398,6994,13396,8193,20399,19399,3392,16792,18199,5001,6800,5992,20603,18403,19596,12804,6405,1994,2605,8402,12392,7793,4802,15202,12200,3597,15792,9397,8992,17200,18805,16603,12001,13004,5601,7194,6199,10799,8604,7403,10595,6593,13197,4601,3800,19999,16197,19193,4405,15596,17605,19798,13994,2196,10401,13792,21200,21003,9797,21604,5202,17994,17792,14398,20205,21398,9598,18597,11800,11405,5393,2800,14992,2394,12596,20792,17000,7597,15998,3996,14204,9199,7994,18200,3800,1402,10000,12403,14000,16002,5203,13802,15403,6602,12001,4801,9803,7202,1601,3200,8803,2602,16203,2400,18603,7601,12601,16400,10603,20002,6200,8002,17602,7001,15800,9603,4001,10202,7400,19002,3001,1800,6403,13601,8400,9401,8600,16600,2200,15603,14401,4201,5800,11002,11202,17203,17001,9200,15003,18802,3603,19800,1202,19602,12201,4602,5602,11801,5402,18403,7800,13002,17402,12800,17801,14203,19203,14601,10802,19402,13402,11403,6002,18001,11603,10403,5000,2802,9003,2001,13200,6802,4400,16801,3401,8202,14800,15200,8518,19914,12528,2517,13923,5718,15327,6114,16329,6524,18318,16518,14315,12926,20731,7329,19733,3130,3527,18915,4514,15526,7719,4729,2924,20319,16723,12718,5329,9131,6324,16129,15721,18726,13721,5915,3316,20925,18529,21121,11724,7915,13322,9924,11314,14119,10732,2316,7527,4918,8926,19123,2725,15125,8718,19321,10518,10329,10119,14523,12314,8115,18117,21331,9724,17517,20528,14928,2122,13527,17731,10929,7132,9531,4323,9321,6721,11928,3916,19515,13120,20127,16917,5129,11131,21715,1930,4132,17132,17318,6919,15932,12132,21533,8330,5523,14728,11523,17914,3729];